Sinh ra ở thủ đô Yaoundé của Cameroon, thời thơ ấu Milla phải chuyển chỗ ở thường xuyên do cha ông làm trong ngành đường sắt. Năm 13 tuổi, ông ký hợp đồng với câu lạc bộ đầu tiên ở Douala. Năm 18 tuổi, ông có được danh hiệu vô địch quốc gia đầu tiên với một câu lạc bộ khác ở Douala.

Năm 1976, khi đang khoác áo Tonnerre Yaoundé, ông nhận được danh hiệu Cầu thủ xuất sắc nhất châu Phi.

Năm 1977, ông chuyển sang châu Âu thi đấu. Đầu tiên là câu lạc bộ Pháp Valenciennes. Tuy nhiên, ông chỉ thi đấu ở đây trong 2 năm. Năm 1979, Milla chuyển đến AS Monaco nhưng thường bị chấn thương hoặc ngồi ghế dự bị. Năm sau ông chuyển tới Bastia nhưng thành công vẫn chưa đến. Chỉ khi đến Saint-Etienne năm 1984, Milla mới thể hiện được tài năng. Sau đó ông cũng giữ vị trí chủ chốt trong đội hình Montpellier từ 1986 đến 1989 và trở thành thành viên ban huấn luyện đội bóng này sau khi không chơi bóng ở Pháp.